#include <stdlib.h>
#include <stdio.h>
#include "uf.h"

struct sUnion_find
{
	tufset * rep;
	int cant;
};

/* FUNCIÓN AUXILIAR (¡NO SE EXPORTA!)*/
Bool
is_rep(const union_find uf, const tufpos i);
/* -------------------------------- */

union_find
uf_create(const tufpos max)
{
	union_find uf;

	uf = (union_find) malloc (sizeof(struct sUnion_find));
	if (uf!=NULL)
	{
		uf->rep = (tufset *) calloc (max+1, sizeof(tufset));
		if (uf->rep!=NULL)
		{	
			uf->cant = 0;
			uf->rep[0] = max;
		}
		else
		{
			free(uf);
			uf = NULL;
			perror("No hay memoria para el array de representantes (uf_create)");
			exit(EXIT_FAILURE);
		}
	}
	else
	{
		perror("No hay memoria para estructura union_find (uf_create)");
		exit(EXIT_FAILURE);
	}
return uf;
}		 


void
uf_add_singulete(union_find uf, const tufalpha el)
{
	tufpos pos;
	pos = el;
	if (uf->rep[pos] == 0)
	{
		uf->rep[pos] = -1;
		uf->cant += 1;
	}
} 


tufset
uf_find(union_find uf, const tufalpha el) /*devuelve el representante del conjunto al cual pertenece el*/
{
	tufpos j,k;
	tufset r;

	j = el;
	while (!(is_rep(uf,j)))
		j = uf->rep[j];
	
	r = j;
	j = el;
	while (!(is_rep(uf,j))) /*acá se hace la compresión de caminos */
	{
		k = uf->rep[j];
		uf->rep[j] = r;
		j = k;
	}
return r;
}

void
uf_union(union_find uf, const tufset s1, const tufset s2)
{
	if (is_rep(uf,s1) && is_rep(uf,s2) && s1!=s2)
	{
		if (uf->rep[s1] >= uf->rep[s2]) /*s1 representa mas elementos por negativos */
		{
			uf->rep[s2] += uf->rep[s1];
			uf->rep[s1] = s2;
		}
		else
		{
			uf->rep[s1] += uf->rep[s2];
			uf->rep[s2] = s1;
		}
		uf->cant -= 1;
	}
}
		

Bool
uf_oneset(const union_find uf)
{
	Bool b;
	b = (uf->cant == 1);
return b;
}

union_find
uf_destroy(union_find uf)
{
	if (uf!=NULL)
	{
		if (uf->rep!=NULL)
		{
			free(uf->rep);
			uf->rep = NULL;
		}
		free(uf);
		uf = NULL;
	}
return uf;
} 

Bool
is_rep(const union_find uf, const tufpos i)
{
	Bool b;
	b = (uf->rep[i] < 0);
return b;
}
